package com.objcat.playground.leetcode;

import java.util.ArrayList;

/**
 * description: Solution22 <br>
 * date: 2022/3/15 12:30 PM <br>
 * author: objcat <br>
 * version: 1.0 <br>
 */
public class Solution23 {

    /**
     * description: isPalindrome2 <br>
     * version: 1.0 <br>
     * date: 2022/3/16 12:00 PM <br>
     * author: objcat <br>
     * @param head
     * @return boolean
     * 执行用时：4 ms, 在所有 Java 提交中击败了 82.93% 的用户
     * 内存消耗：57.6 MB, 在所有 Java 提交中击败了 23.41% 的用户
     */
    public boolean isPalindrome2(ListNode head) {
        // 获取数量
        int count = count(head);
        // 判断边界
        if (count <= 0) {
            return false;
        }
        for (int i = 0; i < count / 2; i++) {
            ListNode a = index(head, i);
            ListNode b = index(head, count - i - 1);
            if (a.val != b.val) {
                return false;
            }
        }
        return true;
    }

    public boolean isPalindrome(ListNode head) {
        ListNode fast = head, slow = head;

        // 快慢指针找中心点
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        // 如果fast不等于null, 说明是奇数
        // 由于奇数中间有一位是不对称的, 所以要从下一位开始比对
        if (fast != null) {
            // 如果是奇数, 中心点需要加1
            slow = slow.next;
        }

        // 反转链表
        slow = reverse(slow);

        // 反转后进行一一对比
        while (slow != null) {
            if (head.val != slow.val) {
                return false;
            }
            head = head.next;
            slow = slow.next;
        }

        return true;
    }

    public ListNode reverse(ListNode node) {
        ListNode prev = null;
        while (node != null) {
            // 获取下一个节点
            ListNode next = node.next;
            // 把prev拼接在后面
            node.next = prev;
            // prev切换到当前节点
            prev = node;
            // 当前节点切换成下一个节点
            node = next;
        }
        return prev;
    }

    public ListNode index(ListNode head, int index) {
        for (int i = 0; i < index; i++) {
            head = head.next;
        }
        return head;
    }

    public int count(ListNode head) {
        if (head == null) {
            return 0;
        }
        int count = 0;
        while (true) {
            count++;
            if (head.next == null) {
                break;
            }
            head = head.next;
        }
        return count;
    }


    public static void main(String[] args) throws InterruptedException {
        ArrayList<Integer> list1 = new ArrayList<>();
        list1.add(1);
        list1.add(1);
        list1.add(2);
        list1.add(1);

//        for (int i = 0; i < 1000; i++) {
//            list1.add(1);
//        }


        ListNode node1 = ListNode.createNode(list1);
        System.out.println(node1);
        long start = System.currentTimeMillis();
        Solution23 solution22 = new Solution23();
        System.out.println(solution22.isPalindrome(node1));
        long end = System.currentTimeMillis();
        System.out.println((end - start) / 1000.0);
    }
}
